其實區間求和相關的內容還有分塊法和莫隊算法，不過 leetcode 上的題目不多，相對冷門，而且大部分題目也都能用前幾天講到的方法來解，所以就跳過了。

今天來對區間求和做個整理。

區間問題可以想像成對線段的操作，主要有兩個動作：修改和查詢；這兩個動作的範圍有兩種：單點和區間。

解法我們則是講了四種：

1. 前綴和(prefix sum)
2. 差分
3. 線段樹(segment tree)
4. 樹狀數組(binary indexed tree/BIT)

組合起來是下面幾種情況：

• 基本題
  • 單點修改，單點查詢：不用技巧，直接操作
  • 區間修改，無查詢：差分
  • 無修改，區間查詢：前綴和／線段樹／樹狀數組
• 進階題
  • 單點修改，區間查詢：線段樹／樹狀數組
  • 區間修改，單點查詢：線段樹／差分
  • 區間修改，區間查詢：線段樹

這些算法很多時候能互通，可以一題多解，當然能用簡單的就沒必要用難的（前綴和能解有什麼理由去造線段樹呢）。重要的是了解這四種算法，然後有一個基本的概念，遇到問題可以先分析是哪種情況，然後再找方法實作出來。

• Current count: 5
• 明天要看隊列或棧還是進去 DP 大坑QQ